package leetcode.datastructure.array;

public class Program134GasStation {
    public Program134GasStation() {
    }
    public int canCompleteCircuit(int[] gas, int[] cost) {
//        return person(gas, cost);
//        return office(gas, cost);
        return fast(gas, cost);
    }

    public int fast(int[] gas, int[] cost) {
        // greedy
        int sum = 0;
        int min = Integer.MAX_VALUE;
        int minIndex = -1;
        for(int i = 0; i < gas.length; i++){
            sum = sum + gas[i] - cost[i];
            if(sum < min ){
                min = sum;
                minIndex = i;//油量最紧缺的点是最后一站
            }
        }
        if(sum < 0){ //无解情况
            return -1;
        }
        return (minIndex + 1) % gas.length; // minIndex + 1 为起点站

    }


    public int office(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
    }

    public int person(int[] gas, int[] cost) {
        int length = gas.length;
        for (int i = 0; i <length; i++) {
            if (cost[i] > gas[i]) {
                continue;
            }
            int oil = gas[i] - cost[i];
            int j = (i + 1) % length;
            while (j != i) {
                // 计算比较多
                if (oil + gas[j] < cost[j]) {
                    break;
                }
                oil +=  gas[j] - cost[j];
                j = (j + 1) % length;
            }
            if (i == j) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Program134GasStation obj = new Program134GasStation();
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        System.out.println(obj.canCompleteCircuit(gas, cost));
        int[] gas1 = {2,3,4};
        int[] cost1 = {3,4,3};
        System.out.println(obj.canCompleteCircuit(gas1, cost1));
    }
}
